package a12_SeqList.ArrayList;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * @Author quan
 * @Description SeqList接口的实现类
 * @Date 2023/3/11 21:51
 */

public class MyArray<E> implements SeqList<E> {
    /**
     * 定义一个泛型数组elementData，使用Object类型
     * size不仅表示现有数组实际存储的大小,还表示下一个元素的位置
     */
    private Object[] elementData;//定义一个泛型数组
    private int size;//定义一个默认的数组大小
    /**
     * 有参和无参构造方法
     */
    //无参构造: 默认数组的长度是10
    public MyArray() {
        this(10);
    }
    //有参构造: 传入参数确定动态数组的长度为size
    public MyArray(int size) {
        this.elementData = new Object[size];
    }
    /**
     * 尾插：直接给数组添加元素
     */
    @Override
    public void add(E element) {
        this.elementData[size] = element;
        size++;
        if(size==elementData.length){
            grow();
        }
    }
    /**
     * 自定义实现grow扩容方法
     * 思想：
*          获取数组原来的旧长度，定义数组扩容后的新长度，定义新数组，长度为扩容后的长度，并将旧数组的
     * 元素值拷贝过来，此时的新数组就是我们的数组。
     */
    private void grow() {
        int oldLength = elementData.length;//获取原数组的长度
        int newLength = oldLength<<1;//获取新数组的长度：默认将容量扩为原先的一倍
        Object[] newArray = Arrays.copyOf(elementData, newLength);//将原数组拷贝到新数组中
        elementData = newArray;//获取扩容后的数组
    }
    /**
     * 三步原则：判断索引合法性——>数据处理：增删改查操作——>判断是否需要扩容
     * 增：根据索引添加元素
     * 思想：判断索引的合法性——>判断根据索引插入元素的位置判断是否需要扩容：
     *     (1)如果index=size,插入位置在size,不需要扩容:直接调用尾插方法
     *     (2)如果0<index<size插入位置在中间：遍历数组，找到索引位置，将索引后的数组元素每个都向后移动一位，就可以将索引位置空出来
     * 然后再将元素添加到索引位置。——>添加完成后判断是否需要扩容
     */
    @Override
    public void add(int index, E element) {
        //(1)判断索引的合理性
        if(index<0||index>size){
            throw new IllegalArgumentException("add index illegal");
        }
        //(2)如果插入位置为尾插：则直接调用尾插方法并提前结束该方法
        if(index==size){
            add(element);
            return;
        }
        //(3)如果插入位置在元素中间，则将数据插入并判断数组长度是否需要扩容
        for (int i = size-1; i >=index; i--) {//遍历数组走到Index位置
            elementData[i+1] = elementData[i];//将Index后的元素向后移
        }
        elementData[index]=element;//此时Index空出，插入待添加的元素
        //(4)判断数组是否需要扩容
        size++;
        if(size==elementData.length){
            grow();
        }
    }

    /**
     * 删：通过索引删除元素
     * 思路：遍历数组走到index位置，获取要删除的元素值进行记录，并将索引后的元素向左移动一位进行元素的覆盖
     */
    @Override
    public E removeByIndex(int index) {
        //(1)判断索引的合法性
        if(!indexCheck(index)){
           throw  new IllegalArgumentException("remove index illegal");
        }
        //(2)获取要删除索引位置的元素
        E oldVal = (E)elementData[index];
        //(2)遍历数组从Index位置走到size
        for (int i = index; i < size-1; i++) {//注意：这里因为要保证索引不能越界：i+1实际上是取不到size的,也就是i<size-1
            elementData[i] = elementData[i+1];//将索引后的元素向左移动一位进行元素的覆盖
        }
        //(3)size--
        size--;
        return oldVal;
    }
    /**
     * 索引的合法性校正
     */
    private boolean indexCheck(int index){
        if(index<0 || index>=size){
            return false;
        }
        return true;
    }
    /**
     * 删：直接删除数组中的出现的第一个element
     * 思路：遍历数组从0索引开始一直判断元素值是否等于element。如果找到了element，则该元素是我们要删除的元素
     * 获取element位置下的Index，通过调用removeByIndex方法删除。size--。
     */
    @Override
    public void removeByValue(E element) {
        for (int i = 0; i < size; i++) {
            if(elementData[i].equals(element)){
                removeByIndex(i);
                return;
            }
        }
        throw new IllegalArgumentException("没有找到该元素~");
    }
    /**
     * 删：删除数组中所有值为element的元素：
     * 错误写法：去掉removeByValue方法中的return即可
     * 原因：当数组中要删除的元素是连续出现时(比如连续出现了3次222)，调用removeByIndex方法删除元素要考虑当前指向的元素是不是要删除的元素：
     * 如果是要删除的元素，则i不能变化
     * 如果不是要删除的元素,i才可以++；
     */
    @Override
    public void removeAllValue(E element) {
//         自己一开始写成了这种形式，当出现连续要删除的元素值时会发生漏删的现象
      /*  for (int i = 0; i < size; i++) {
            if(elementData[i].equals(element)){
                removeByIndex(i);
            }
        }*/
        for (int i = 0; i < size; ) {
            if(elementData[i].equals(element)){
                removeByIndex(i);
            }else{
                i++;
            }
        }
    }
    /**
     * 改：修改index位置下的元素为element，并返回被修改的原值
     */
    @Override
    public E set(int index, E element) {
        if(!indexCheck(index)){
            throw new IllegalArgumentException("set index illegal");
        }
        //找到index下的旧值返回,并将新的数值赋值给数组的index位置
        E oldVal = (E)elementData[index];
        elementData[index] = element;
        return oldVal;

    }
    /**
     * 查：查询索引Index位置下的元素
     */
    @Override
    public E get(int index) {
        //(1)判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("get index illegal");
        }
        //(2)返回数值
        return (E) elementData[index];
    }

    /**
     * 判断数组是否包含element元素值，返回判断结果
     * 思想：遍历数组0-size,将数组的每一个值与element进行比对
     */
    @Override
    public boolean contains(E element) {
        for (int i = 0; i < size; i++) {
            if(elementData[i].equals(element)){
                return true;
            }
        }
        return false;
    }
    /**
     * 返回元素element在数组中对应的索引
     */
    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if(elementData[i].equals(element)){
                return i;
            }
        }
        throw new IllegalArgumentException("indexOf error"+"Don't has this element");
    }
    /**
     * 重写ToString方法
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        // 遍历elementData数组
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
